#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <bitset>
#include <utility>
using namespace std;

#define mm(a, n) memset(a, n, sizeof a)
#define mk(a, b) make_pair(a, b)

const double eps = 1e-6;
const int INF = 0x3f3f3f3f;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<int, LL> PIL;

inline void quickread() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

// int n;
// stack<int> stk;
// vector<int> v;
// 
// inline void solution() {
//     cin >> n;
//     getchar();
//     for (int i = 0; i < n; i ++ ) {
//         string s;
//         getline(cin, s);
//         if (s[1] == 'o') {
//             // Pop
//             if (!stk.empty()) {
//                 v.erase(lower_bound(v.begin(), v.end(), stk.top()));
//                 printf("%d\n", stk.top());
//                 stk.pop();
//             } else {
//                 printf("Invalid\n");
//             }
//         } else if (s[1] == 'u') {
//             // Push
//             int t = stoi(s.substr(5));
//             stk.push(t);
//             v.insert(lower_bound(v.begin(), v.end(), t), t);
//         } else {
//             // PeekMedian
//             if (!stk.empty()) {
//                 int pos = v.size() % 2 == 0 ? v.size() / 2 : (v.size() + 1) / 2;
//                 cout << v[pos - 1] << endl;
//                 printf("%d\n", v[pos - 1]);
//             } else {
//                 printf("Invalid\n");
//             }
//         }
//     }
// }


int n;
stack<int> stk;
multiset<int> up, down;

void adjust() {
    while (up.size() > down.size()) {
        auto it = up.begin();
        down.insert(*it);
        up.erase(it);
    } 

    while (up.size() + 1 < down.size() ) {
        auto it = down.end();
        it --;
        up.insert(*it);
        down.erase(it);
    }
}

inline void solution() {
    cin >> n;
    getchar();
    for (int i = 0; i < n; i ++ ) {
        string s;
        getline(cin, s);
        if (s[1] == 'o') {
            // Pop
            if (!stk.empty()) {
                int x = stk.top(); stk.pop();
                printf("%d\n", x);
                auto it = down.end(); it -- ;
                // 上面的可能不存在值，但下面一定存在值
                if (x <= *it) down.erase(down.find(x));
                else  up.erase(up.find(x));
                adjust();
            } else {
                printf("Invalid\n");
            }
        } else if (s[1] == 'u') {
            // Push
            int t = stoi(s.substr(5));
            stk.push(t);
            if (up.empty() || t <= *up.begin()) down.insert(t);
            else up.insert(t);
            adjust();
        } else {
            // PeekMedian
            if (!stk.empty()) {
                auto it = down.end();
                it --;
                printf("%d\n", *it);
            } else {
                printf("Invalid\n");
            }
        }
    }
    return ;
}

int main() {
    freopen("input.txt", "r", stdin);
    quickread();
    solution();
    return 0;
}